By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 37, Issue 5, pp. 1299-1701

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Oracles for Distances Avoiding a Failed Node or Link

Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, and Vijaya Ramachandran

pp. 1299-1318

BibTeX  Abstract Full Text:  PDF

A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game

Jochen Könemann, Stefano Leonardi, Guido Schäfer, and Stefan H. M. van Zwam

pp. 1319-1341

BibTeX  Abstract Full Text:  PDF

The Forgetron: A Kernel-Based Perceptron on a Budget

Ofer Dekel, Shai Shalev-Shwartz, and Yoram Singer

pp. 1342-1372

BibTeX  Abstract Full Text:  PDF

On $k$-d Range Search with Patricia Tries

Bradford G. Nickerson and Qingxiu Shi

pp. 1373-1386

BibTeX  Abstract Full Text:  PDF

Quantum Property Testing

Harry Buhrman, Lance Fortnow, Ilan Newman, and Hein Röhrig

pp. 1387-1400

BibTeX  Abstract Full Text:  PDF

Compression in Finite Fields and Torus-Based Cryptography

K. Rubin and A. Silverberg

pp. 1401-1428

BibTeX  Abstract Full Text:  PDF

Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems

Ivona Bezáková, Daniel Štefankovič, Vijay V. Vazirani, and Eric Vigoda

pp. 1429-1454

BibTeX  Abstract Full Text:  PDF

Improved Dynamic Reachability Algorithms for Directed Graphs

Liam Roditty and Uri Zwick

pp. 1455-1471

BibTeX  Abstract Full Text:  PDF

A Faster, Better Approximation Algorithm for the Minimum Latency Problem

Aaron Archer, Asaf Levin, and David P. Williamson

pp. 1472-1498

BibTeX  Abstract Full Text:  PDF

Optimal Power-Down Strategies

John Augustine, Sandy Irani, and Chaitanya Swamy

pp. 1499-1516

BibTeX  Abstract Full Text:  PDF

Splitting NP-Complete Sets

Christian Glaßer, A. Pavan, Alan L. Selman, and Liyu Zhang

pp. 1517-1535

BibTeX  Abstract Full Text:  PDF

Learning Mixtures of Product Distributions over Discrete Domains

Jon Feldman, Ryan O'Donnell, and Rocco A. Servedio

pp. 1536-1564

BibTeX  Abstract Full Text:  PDF

Holographic Algorithms

Leslie G. Valiant

pp. 1565-1594

BibTeX  Abstract Full Text:  PDF

Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling

Ho-Leung Chan, Tak-Wah Lam, and Kin-Shing Liu

pp. 1595-1612

BibTeX  Abstract Full Text:  PDF

Randomization Does Not Reduce the Average Delay in Parallel Packet Switches

Hagit Attiya and David Hay

pp. 1613-1636

BibTeX  Abstract Full Text:  PDF

A Practical Shortest Path Algorithm with Linear Expected Time

Andrew V. Goldberg

pp. 1637-1655

BibTeX  Abstract Full Text:  PDF

Stability of Load Balancing Algorithms in Dynamic Adversarial Systems

Elliot Anshelevich, David Kempe, and Jon Kleinberg

pp. 1656-1673

BibTeX  Abstract Full Text:  PDF

The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case

Hubie Chen

pp. 1674-1701

BibTeX  Abstract Full Text:  PDF